#include <vector>
using namespace std;
/*
 * @lc app=leetcode.cn id=221 lang=cpp
 *
 * [221] 最大正方形
 */

// @lc code=start
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int rows = matrix.size(), columns = matrix[0].size(), res = 0;
        vector<vector<int>> dp(rows, vector<int>(columns, 0));
        auto get = [&](int x, int y) -> int {
            if (x < 0 || y < 0) return 0;
            return dp[x][y];
        };

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') dp[i][j] = min(get(i - 1, j), min(get(i, j - 1), get(i - 1, j - 1))) + 1;
                else dp[i][j] = 0;
                res = max(res, dp[i][j]);
            }
        }
        return res * res;
    }
};
// @lc code=end

